/*
 * @lc app=leetcode.cn id=427 lang=golang
 * @lcpr version=30118
 *
 * [427] 建立四叉树
 */

// @lcpr-template-start

package main

import "fmt"

func main() {
	// grid := [][]int{
	// 	{0, 1},
	// 	{1, 0},
	// }
	grid := [][]int{
		{1, 1, 1, 1, 0, 0, 0, 0},
		{1, 1, 1, 1, 0, 0, 0, 0},
		{1, 1, 1, 1, 1, 1, 1, 1},
		{1, 1, 1, 1, 1, 1, 1, 1},
		{1, 1, 1, 1, 0, 0, 0, 0},
		{1, 1, 1, 1, 0, 0, 0, 0},
		{1, 1, 1, 1, 0, 0, 0, 0},
		{1, 1, 1, 1, 0, 0, 0, 0},
	}
	fmt.Println(construct(grid))
}

type Node struct {
	Val         bool
	IsLeaf      bool
	TopLeft     *Node
	TopRight    *Node
	BottomLeft  *Node
	BottomRight *Node
}

// @lcpr-template-end
// @lc code=start

func construct(grid [][]int) *Node {
	if len(grid) == 0 {
		return nil
	}
	return dfs(grid, 0, len(grid)-1, 0, len(grid[0])-1)
}

func dfs(grid [][]int, rstart int, rend int, cstart int, cend int) *Node {
	if rstart == rend {
		return &Node{
			Val:         grid[rstart][cstart] == 1,
			IsLeaf:      true,
			TopLeft:     nil,
			TopRight:    nil,
			BottomLeft:  nil,
			BottomRight: nil,
		}
	}
	root := &Node{Val: true, IsLeaf: false}
	root.TopLeft = dfs(grid, rstart, (rstart+rend)/2, cstart, (cstart+cend)/2)
	root.TopRight = dfs(grid, rstart, (rstart+rend)/2, (cstart+cend)/2+1, cend)
	root.BottomLeft = dfs(grid, (rstart+rend)/2+1, rend, cstart, (cstart+cend)/2)
	root.BottomRight = dfs(grid, (rstart+rend)/2+1, rend, (cstart+cend)/2+1, cend)
	if root.TopLeft.IsLeaf &&
		root.TopRight.IsLeaf &&
		root.BottomLeft.IsLeaf &&
		root.BottomRight.IsLeaf {
		if root.TopLeft.Val == root.TopRight.Val &&
			root.TopRight.Val == root.BottomLeft.Val &&
			root.BottomLeft.Val == root.BottomRight.Val {
			root.Val = root.TopLeft.Val
			root.IsLeaf = true
			root.TopLeft = nil
			root.TopRight = nil
			root.BottomLeft = nil
			root.BottomRight = nil
		}
	}
	return root
}

// @lc code=end

/*
// @lcpr case=start
// [[0,1],[1,0]]\n
// @lcpr case=end

// @lcpr case=start
// [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]\n
// @lcpr case=end

*/
